//
//  Tree.swift
//  Maze24
//
//  Created by Mars on 2020/11/14.
//

import Foundation


class Tree {
  
  var node: Token
  
  var left: Tree?
  var right: Tree?
  
  var isReplaced = false
  
  init(node: Token, left: Tree? = nil, right: Tree? = nil) {
    self.node = node
    self.left = left
    self.right = right
  }
  
  var isLeaf: Bool { left == nil && right == nil }
  
  func calculate() -> Int {
    if isLeaf {
      switch node {
        case .operator:
          return 0
        case .operand(let n):
          return n
      }
    }
    
    let l = left?.calculate() ?? 0
    let r = right?.calculate() ?? 0
    
    if case Token.operator(let op) = node {
      switch op {
        case .add:
          return l + r
        case .sub:
          return l - r
        case .mul:
          return l * r
        case .div:
          if r == 0 { return 0 }
          return l / r
      }
    }
    
    return 0 // We should never get here.
  }
  
  func traverseLeaves(parent: Tree, action: (Tree, Int) -> Void) -> Void {
    if left != nil {
      left!.traverseLeaves(parent: self, action: action)
    }
    
    if right != nil {
      right!.traverseLeaves(parent: self, action: action)
    }
    
    if isLeaf {
      if self.calculate() == parent.left!.calculate() {
        return action(parent, 1)
      }
      else if self.calculate() == parent.right!.calculate() {
        return action(parent, 2)
      }
      
    }
  }
  
  init(from tokens: [Token]) {
    node = tokens[1]
    left = Tree(node: tokens[0])
    right = Tree(node: tokens[2])
    
    for i in stride(from: 3, to: tokens.count - 2, by: 3) {
      let tmp = Tree(node: tokens[i+1])
      tmp.left = Tree(node: tokens[i])
      tmp.right = Tree(node: tokens[i+2])
      let tmpValue = tmp.calculate()
      
      traverseLeaves(parent: self) { t, s in
        if s == 1 {
          if case Token.operand(let value) = t.left!.node, tmpValue == value {
            t.left = tmp
          }
        }
        else if s == 2 {
          if case Token.operand(let value) = t.right!.node, tmpValue == value {
            t.right = tmp
          }
        }
      }
    }
  }
  
  func expression() -> String {
    var str = ""
    
    if !isLeaf {
      str += "("
    }
    
    str += (left?.expression() ?? "")
    
    if isLeaf, case Token.operand(let n) = node {
      str += String(n)
      return str
    }
    
    if case Token.operator(let op) = node {
      str += op.rawValue
    }
    
    str += (right?.expression() ?? "")
    
    if !isLeaf {
      str += ")"
    }
    
    return str
  }
}
